package com.hdu.other.dp.shuweiDp;


public class lc902 {
    class Solution {
        public int atMostNGivenDigitSet(String[] digits, int n) {

            int len = 1;
            int offset = 1;
            int tmp = n / 10;
            while (tmp > 0) {
                len++;
                offset *= 10;
                tmp /= 10;
            }

            int[] nums = new int[digits.length];
            for (int i = 0; i < digits.length; i++) {
                nums[i] = Integer.parseInt(digits[i]);
            }
            return f(nums, n, len, offset, 0, 0);
        }

        int f(int[] nums, int n, int len, int offset, int fix, int free)
        {
            if (len == 0)
            {
                return fix == 1 ? 1 : 0;
            }
            int ans = 0;
            if (fix == 0)
            {
                ans += f(nums, n, len - 1, offset / 10, 0, 1);
            }
            int cur = (n / offset) % 10;
            if (free == 0)
            {
                for (int i : nums)
                {
                    if (i < cur)
                    {
                        ans += f(nums, n, len - 1, offset / 10, 1, 1);
                    }
                    else if (i == cur)
                    {
                        ans += f(nums, n, len - 1, offset / 10, 1, 0);
                    }
                    else {
                        break;
                    }
                }
            }
            else
            {
                ans += nums.length * f(nums, n, len - 1, offset / 10, 1, 1);
            }
            return ans;
        }
    }
}
